from math import sqrt
from tools_algorithm import *


class Solution:
    def minNumberOfSeconds(self, mountainHeight: int, workerTimes: List[int]) -> int:

        def f(t):
            tot = 0
            for w in workerTimes:
                c = -(t * 2) / w
                d = 1 - 4 * c
                x = (-1 + sqrt(d)) / 2
                tot += x

            return tot >= mountainHeight

        return bisect_left(range(10**16), True, key=f)


class Solution:
    def minNumberOfSeconds(self, mountainHeight: int, workerTimes: List[int]) -> int:
        ans = 0
        q = []
        for w in workerTimes:
            q.append([w, 2, w])
        heapify(q)
        for _ in range(mountainHeight):
            t, c, w = heappop(q)
            ans = t
            heappush(q, [t + w * c, c + 1, w])
        return ans


s = Solution()
print(s.minNumberOfSeconds(10, [4]))


class Solution:
    def validSubstringCount(self, word1: str, word2: str) -> int:
        c2 = Counter(word2)
        limit = 0
        for k in c2.keys():
            limit |= 1 << (ord(k) - ord("a"))
        c1 = Counter()
        stat = 0
        l = 0
        ans = 0
        f = False
        for v in word1:
            c1[v] += 1
            if c1[v] >= c2[v]:
                stat |= 1 << (ord(v) - ord("a"))
                if stat & limit == limit:
                    f = True
                    while stat & limit == limit:
                        lv = word1[l]
                        c1[lv] -= 1
                        if (
                            c1[lv] < c2[lv]
                            and (stat >> (ord(word1[l]) - ord("a")) & 1) == 1
                        ):
                            stat ^= 1 << (ord(word1[l]) - ord("a"))
                        l += 1
            if f:
                ans += l
        return ans


s = Solution()
print(
    s.validSubstringCount(
        "wfkzxeimdkiwjjyrmldyjlqioxwljmewriefgcpmdzhzmxnupezrhntxiyclrjlgjhbdnpeajicerrkxvaiciuxfbfozuzqxhpprakjepjalgvfbhdfgzxbqgucdxckjwxjacdbxcbobdopyywjpatkjrpjmsrqcesgfkrkgflzsqmdguhswtilbfesqpucsfctpgurfwfrwvovjusbxgphoxxpuajdicxxdusdiijlvrxtxcieiptxpndwhdcnhxmocyliqktglwayywcoqjppatnzisdawzyyxrjxtrgljhcixrumpnjeghsmjgamkgmbvfhdysejfeqxlrsxyiljxjclnhqskerwehqyuztobnoesflprradwbhetehawjmzpsqhdhhxxcqwdmcsflbplmymodgemiaahvrjvswphurrtlgkcotdnppmufsvvlfsjhoofzdiwbabxtyrmrgohvrowduwgemsbvcdmjzmzadfpbkachqvnzpcktixzktcwyjwvqorwbvlduqniurgvulcqgbxkrxxmzdvkcijvedrdirkxomyrmqxffiojhdnddyjpnzltxucndkcrgtdyyrnxqzwgzeobpagbbyrlxcixycxdqbjffqhyhrooccpxhlktcmwhtksvbjcnecbqecheskjmcrapfmgjriezkjmjbndpyzygnkdozvkdaionkljmfajmelmjovceyzkwanylhjvwjhurbtqvgpjwwvgovnxnouperesgqbkqxnsjumhfachcvnqzcacbxoueaxjlcjkmkrirgysbxyypkzrhryolwwmcsxicwzlhurlnbymtbljsaxmwqjdccxxujqpwnxhrsrhhtaxpkfncpxgkaflckyzzeyvudwqljohclamqfjwztvjgpfqfcjdsdcarqedborctucqpjtwfbojdyhcxarhykmrymwvbpthhuikoocptkwgzzguzmeeajllbyzsnifjjpiqo",
        "iogvngzpga",
    )
)
# f = test_file_path(__file__, 1)
# ca = []
# c = []
# for _ in range(1000):
#     c.append(chr(random.randint(0, 25) + ord("a")))
# ca.append("".join(c))
# c = []
# for _ in range(10):
#     c.append(chr(random.randint(0, 25) + ord("a")))
# ca.append("".join(c))
# print(ca, file=f)
